package 线;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 滑动窗口最大值
 * @author ycc
 * @date 2025/5/4
 */
public class MaxSlidingWindow {
    public static void main(String[] args) {
        // int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] arr = {1, 3, -1, 2, 2, 2, 6, 7};
        int[] res = maxSlidingWindow(arr, 3);
        System.out.println(Arrays.toString(res));

//        int[] res2 = maxSlidingWindow2(arr, 3);
//        System.out.println(Arrays.toString(res2));
//
//        int[] res4 = maxSlidingWindow4(arr, 3);
//        System.out.println(Arrays.toString(res4));
//        int[] res5 = maxSlidingWindow5(arr, 3);
//        System.out.println(Arrays.toString(res5));

//        int[] res6 = maxSlidingWindow6(arr, 3);
//        System.out.println(Arrays.toString(res6));
//        int[] res7 = maxSlidingWindow7(arr, 3);
//        System.out.println(Arrays.toString(res7));
//        int[] res8 = maxSlidingWindow8(arr, 3);
//        System.out.println(Arrays.toString(res8));

//        int[] res10 = maxSlidingWindow9(arr, 3);
//        System.out.println(Arrays.toString(res10));
        int[] res11 = maxSlidingWindow11(arr, 3);
        System.out.println(Arrays.toString(res11));
    }

    public static int[] maxSlidingWindow11(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);

            int w = i - k + 1;

            if(w < 0) {
                continue;
            }
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            maxes[w] = nums[deque.peekFirst()];
        }
        return maxes;
    }

    public static int[] maxSlidingWindow10(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            int w = i - k + 1;
            if(w < 0) {
                continue;
            }
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            maxes[w] = nums[deque.peekFirst()];
        }
        return maxes;
    }

    public static int[] maxSlidingWindow9(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            int w = i - k + 1;
            if(w < 0) {
                continue;
            }
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            maxes[w] = nums[deque.peekFirst()];
        }
        return maxes;
    }

    public static int[] maxSlidingWindow8(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            int w = i - k + 1;
            if(w < 0) {
                continue;
            }
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            maxes[w] = nums[deque.peekFirst()];
        }
        return maxes;
    }

    /**
     * 滑动窗口最大值
     * @param nums
     * @param k
     * @return
     * 滑动窗口的数量等于数组长度减去窗口大小加 1
     * 双端队列（Deque）的作用
     * 作用：维护一个双端队列，存储可能成为当前或未来窗口最大值的元素的索引
     * 队列性质：
     * 队列中的索引对应的数组值是单调递减的（队首是当前窗口的最大值）。
     * 队列中索引对应的元素始终在滑动窗口范围内。
     * 1. 移除队列中不可能成为最大值的元素
     * 操作：从队尾开始，移除所有小于等于当前元素 nums[i] 的索引。
     * 目的：确保队列是单调递减的，且当前元素 nums[i] 可能是未来窗口的最大值。
     * 2. 将当前索引入队
     * 将当前索引 i 加入队尾（因为它可能成为后续窗口的最大值）
     * 3. 检查队首是否在窗口内
     * w 是当前窗口的起始索引（i 是窗口的结束索引）。
     * 如果 w < 0，说明窗口还未完全进入数组，跳过最大值记录。
     * 4. 移除过期队首元素
     * 如果队首索引 deque.peekFirst() 已经不在当前窗口内（即 deque.peekFirst() < w），需要将其移除。
     * 5. 记录当前窗口最大值
     * 队首元素 deque.peekFirst() 是当前窗口的最大值，将其存入结果数组 maxes 的对应位置。
     *
     * 在滑动窗口最大值问题中，确保双端队列（Deque）的队首始终是当前窗口的最大值是关键
     *
     */
    public static int[] maxSlidingWindow7(int[] nums, int k) {
        // 上焦
        // 边界条件处理
        if (nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        // 初始化结果数组
        int[] maxes = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        // 中焦（三阴三阳或五行）
        for(int i = 0; i < nums.length; i++) {
            // 1.移除队列中不可能成为最大值的元素(木）
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            // 2.将当前索引入队（火）
            deque.offerLast(i);

            // 3.检查队首是否在窗口内（土）
            int w = i - k + 1;
            if(w < 0) {
                continue;
            }
            // 4.移除过期元素（金）
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            // 5.记录当前窗口最大值（水）
            maxes[w] = nums[deque.peekFirst()];
        }
        // 下焦
        return maxes;
    }

    /**
     * 滑动窗口最大值
     * @param nums
     * @param k
     * @return
     * 编写函数的三大步：
     * 1.是否存在有参数合法性，
     * 2.操作是否会对内部本身造成影响，
     * 3.具体的功能业务实现
     */
    public static int[] maxSlidingWindow6(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i); // 存入的是元素索引

            int w = i - k + 1;
            if(w < 0) {
                continue;
            }
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            maxes[w] = nums[deque.peekFirst()];
        }
        return maxes;
    }

    /**
     * 滑动窗口最大值
     * 借助双端队列，维护一个窗口，窗口中存放的是索引，从而获取窗口的最大值
     * 技术点： 循环 + 双端队列 + 双指针思想
     * @param nums
     * @param k
     * @return
     * 1. 检查参数
     * 2. 初始化双端队列，存放的是索引
     * 3. 遍历数组，计算滑动窗口的索引，处理维护双端队列中的元素是逐渐减少的
     * 4. 检查窗口索引，赋值窗口的最大值
     */
    public static int[] maxSlidingWindow4(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            // 删除队尾元素
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            // 添加索引
            deque.offerLast(i);
            int w = i - k + 1;
            if(w < 0) {
                continue;
            }
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            maxes[w] = nums[deque.peekFirst()];
        }
        return maxes;
    }

    // 暴力解法 O(n^2)
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        int[] maxes = new int[nums.length - k + 1];
        for (int i = 0; i <= nums.length - k; i++) {
            // 窗口的最大值
            maxes[i] = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                maxes[i] = Math.max(maxes[i], nums[j]);
            }
        }
        return maxes;
    }

    // 滑动窗口最大值
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1) {
            return new int[0];
        }
        if(k == 1) {
            return nums;
        }
        int[] maxes = new int[nums.length - k + 1];

        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++) {
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // 检查窗口的索引是否合法
            int w = i - k + 1;
            if(w < 0) {
                continue;
            }
            // 检查队头的合法性 滑动窗口为什么放索引
            if(deque.peekFirst() < w) {
                deque.pollFirst();
            }
            // 设置窗口的最大值 w是窗口的索引
            maxes[w] = nums[deque.peekFirst()];
        }

        return maxes;
    }
}
